#include "fifo.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


struct Page
{
  char data;
  int stay;
};

/**
 * 函数：模拟FIFO（先进先出）页面置换算法。
 *
 * @param queue_frames 一个字符串，表示页面访问序列。
 *                     字符串中的每个字符是一个数字，表示一个页面号。
 * @param num_frames   页框的数量，表示物理内存中可用的页框数。
 */
void
fifo_page_replacement (char *queue_frames, int num)
{
  // TODO
  // 使用数组记录页表项
  struct Page pages[10];
  // 记录当前内存中的页面数量
  int count = 0;
  for (int i = 0; queue_frames[i] != '\0'; i++)
  {
    // 如果遇到','字符，跳过
    if (queue_frames[i] == ',') continue;
    printf ("Access:%c,", queue_frames[i]);
    int is_exist = 0;
    // 判断该页面是否已在内存中
    for (int k = 0; k < count; k++)
    {
      if (pages[k].data == queue_frames[i])
        is_exist = 1;
    }
    // 不存在，则判断是否需要页面置换
    if (!is_exist)
    {
      // 如果页表未满，添加页面到页表
      if (count < num)
      {
        pages[count].data = queue_frames[i];
        pages[count].stay = 0;
        
        count++;
      }
      // 页表已满，置换stay值最大即驻留时间最长的页面
      else
      {
        int max_idx = 0;
        for (int k = 0; k < num; k++)
        {
          if (pages[k].stay > pages[max_idx].stay)
            max_idx = k;
        }
        pages[max_idx].data = queue_frames[i];
        pages[max_idx].stay = 0;
      }
      // 页面stay值统一+1
      for (int k = 0; k < count; k++)
      {
        pages[k].stay++;
      }
    }
    // 打印页表项
    printf ("Frames: [");
    int cnt = 0;
    for (int k = 0; k < count; k++)
    {
      cnt++;
      printf ("%c", pages[k].data);
      if (cnt != count) printf (",");
    }
    if (cnt < num)
    {
      int pad_num = num - cnt;
      while (pad_num--)
      {
        printf (",-1");
      }
    }
    printf ("]\n");
  }
}

// // 链表模拟队列实现，但打印顺序不对
// typedef struct Node
// {
//   char data;
//   struct Node* next;
// } Node;

// /**
//  * 函数：模拟FIFO（先进先出）页面置换算法。
//  *
//  * @param queue_frames 一个字符串，表示页面访问序列。
//  *                     字符串中的每个字符是一个数字，表示一个页面号。
//  * @param num_frames   页框的数量，表示物理内存中可用的页框数。
//  */
// void
// fifo_page_replacement (char *queue_frames, int num)
// {
//   // TODO
//   // 创建链表头结点统一操作、便于操作
//   Node *head = (Node *)malloc(sizeof(Node));
//   head->next = NULL;
//   Node *tail = head;
//   // 记录当前内存中的页面数量
//   int count = 0;
//   for (int i = 0; queue_frames[i] != '\0'; i++)
//   {
//     // 如果遇到','字符，跳过
//     if (queue_frames[i] == ',') continue;
//     printf ("Access:%c,", queue_frames[i]);
//     int is_exist = 0;
//     Node *p = head->next;
//     // 判断该页面是否已在内存中
//     while (p)
//     {
//       if (p->data == queue_frames[i])
//         is_exist = 1;
//       p = p->next;
//     }
//     // 不存在，则判断是否需要页面置换
//     if (!is_exist)
//     {
//       // 如果页表未满，添加页面到页表
//       if (count < num)
//       {
//         Node *newNode = (Node *)malloc(sizeof(Node));
//         newNode->data = queue_frames[i];
//         newNode->next = tail->next;
//         tail->next = newNode;
//         tail = newNode;
//         count++;
//       }
//       // 页表已满，置换头结点指向的页面
//       else
//       {
//         Node *first = head->next;
//         first->data = queue_frames[i];
//         head->next = first->next;
//         first->next = tail->next;
//         tail->next = first;
//         tail = tail->next;
//       }
//     }
//     p = head->next;
//     // 打印页表项
//     printf ("Frames: [");
//     int cnt = 0;
//     while (p)
//     {
//       cnt++;
//       printf ("%c", p->data);
//       p = p->next;
//       if (p) printf (",");
//     }
//     if (cnt < num)
//     {
//       int pad_num = num - cnt;
//       while (pad_num--)
//       {
//         printf (",-1");
//       }
//     }
//     printf ("]\n");
//   }
//   // 释放堆内存
//   while (head)
//   {
//     Node *tmp = head->next;
//     head->next = NULL;
//     free (head);
//     head = tmp;
//   }
// }
